package leetcode;

/**
 * 穿过此结点，但是不穿过父节点
 */
public class l0124_二叉树中的最大路径和 {

    private Integer sum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        value(root);
        return sum;
    }

    /**
     * 计算node 提供给父节点的最大路径值
     */
    private int value(TreeNode node) {
        //递归出口
        if (node == null) {
            return 0;
        }
        int left = value(node.left);
        left = Math.max(left, 0);
        int right = value(node.right);
        right = Math.max(right, 0);
        sum = Math.max(sum, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}
